Packet-transfer devices in high-speed data networks, such as switches and routers, are required to perform flexible and sophisticated packet classification functions at high speed. For example, Internet routers make packet forwarding decisions by searching for the destination Internet Protocol (IP) addresses of incoming packets in a database known as a routing table. The routing table, rather than storing the full IP addresses, stores only some of the leading portion, known as a prefix. For each incoming packet, the router searches the table for the most specific of the matching table entries, referred to as the longest prefix match (LPM), in which the largest number of leading address bits of the destination IP address match those in the packet.
As another example, many packet-transfer devices apply access control lists (ACLs) in filtering network traffic, and particularly in preventing certain traffic from entering or exiting a network. The filtering criteria listed in the ACL are commonly in the form of classification rules based on packet header information, such as IP source and destination addresses, as well as higher-level protocol information, such as transport-layer port numbers. Many advanced switches and routers have a management interface, which a system administrator can use to program and update the ACL, as well as other data structures and functions.
Classification rules used by a switch or router are typically held in a memory, such as static random-access memory (SRAM) or ternary content-addressable memory (TCAM), as are known in the art. Various schemes have been proposed to promote efficient use of and access to such memory.
For example, U.S. Pat. No. 7,245,623 describes a system and method provide for efficient classification of long strings of data, such as network messages, using hierarchical parallel banks of associative memories. The system, which may be a classification engine for use in a network device, is includes one or more stages having one or more banks of TCAM, which are organized into one or more groups, each processing network messages for a different set of ports of the network device. The system further includes at least one memory resource that is shared by the TCAM banks of all groups. The system is said to process network messages at high speed while minimizing the number of required components.